Existing computer programs known as “road-mapping” programs provide digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the road-mapping program will display an on-screen map of the selected location. Several existing road-mapping products typically include the ability to calculate a “best route” between two locations. In other words, the user can input two locations, and the road-mapping program will compute the travel directions from the source location to the destination location. The directions are typically based on distance, travel time, and certain user preferences, such as a speed at which the user likes to drive, or the degree of scenery along the route. Computing the best route between locations may require significant computational time and resources.
Existing road-mapping programs employ variants of a method attributed to E. Dijkstra to compute shortest paths. Dijkstra's method is described by Cormen, Leiserson and Rivest in Introduction to Algorithms, MIT Press, 1990, pp. 514-531, which is hereby incorporated by reference in its entirety for all that it teaches without exclusion of any part thereof. Note that in this sense “shortest” means “least cost” because each road segment is assigned a cost or weight not necessarily directly related to the road segment's length. By varying the way the cost is calculated for each road, shortest paths can be generated for the quickest, shortest, or preferred routes.
Dijkstra's original method, however, is not always efficient in practice, due to the large number of locations and possible paths that are scanned. Instead, many modern road-mapping programs use heuristic variations of Dijkstra's method, including A* search (a.k.a. heuristic or goal-directed search) in order to “guide” the shortest-path computation in the right general direction. Such heuristic variations typically involve estimating the weights of paths between intermediate locations and the destination. A good estimate reduces the number of locations and road segments that must be considered by the road-mapping program, resulting in a faster computation of shortest paths; a bad estimate can have the opposite effect, and increase the overall time required to compute shortest paths. If the estimate is a lower-bound on distances with certain properties, A* search computes the optimal (shortest) path. The closer these lower-bounds are to the actual path weights, the better the estimation and the algorithm performance. Lower-bounds that are very close to the actual values being bound are said to be “good.” Previously known heuristic variations use lower-bound estimation techniques such as Euclidean distance (i.e., “as the crow flies”) between locations, which are not very good.
More recent developments in road mapping algorithms utilize a two-stage process comprising a preprocessing phase and a query phase. During the preprocessing phase the graph or map is subject to an off-line processing such that later real time queries between any two destinations on the graph can be made more efficiently. Previous examples of preprocessing algorithms use geometric information, hierarchical decomposition, and A* search combined with landmark distances.
Gutman improved existing preprocessing algorithms by introducing the concept of graph pruning based on vertex reach. Gutman teaches pruning vertices from a particular search based on upper bounds of vertex reaches and lower bounds on vertex distances between the search origin and the search destination. Gutman uses Euclidean distances for lower bounds, and combines reach with the existing A* search.
Goldberg and Harrelson have shown that the performance of A* can be improved if landmark-based lower bounds are used instead of Euclidean bounds. These lower bounds are obtained by storing (in the preprocessing step) the distances between every vertex and a small (constant-sized) set of special vertices, the landmarks. During queries, one can use this information, together with the triangle inequality, to obtain lower bounds on the distances between any two vertices in the graph. This leads to the ALT (A* search, landmarks, and triangle inequality) algorithm for the point-to-point problem.
While these methods have resulted in more efficient query phases, these methods are often not practical for very large graphs.
Sanders and Schultes described highway hierarchy and used it to design efficient algorithms for the shortest path problem on road networks. While building the hierarchy structure, these algorithms use a notion of shortcuts. Sanders and Schultes suggested shortcutting not only degree-two vertices, but other vertices of small degree as well.